Longest zigzag path in a binary tree

Time: O(N); Space: O(H); medium

Given a binary tree root, a ZigZag path for a binary tree is defined as follow:

  • Choose any node in the binary tree and a direction (right or left).

  • If the current direction is right then move to the right child of the current node otherwise move to the left child.

  • Change the direction from right to left or right to left.

  • Repeat the second and third step until you can’t move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

Example 1:

Input: root = {TreeNode} [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]

Output: 3

Explanation:

Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = {TreeNode} [1,1,1,null,1,null,null,1,1,null,1]

Output: 4

Explanation:

  • Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]

Output: 0

Constraints:

  • Each tree has at most 50000 nodes..

  • Each node’s value is between [1, 100].

Hints:

  1. Create this function maxZigZag(node, direction) maximum zigzag given a node and direction (right or left).

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. DFS

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def longestZigZag(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node, result):
            if not node:
                return [-1, -1]
            left, right = dfs(node.left, result), dfs(node.right, result)
            result[0] = max(result[0], left[1]+1, right[0]+1)
            return [left[1]+1, right[0]+1]

        result = [0]
        dfs(root, result)

        return result[0]

[3]:

s = Solution1()

root = TreeNode(1)
root.right = TreeNode(1)
root.right.left, root.right.right = TreeNode(1), TreeNode(1)
root.right.right.left, root.right.right.right = TreeNode(1), TreeNode(1)
root.right.right.left.right = TreeNode(1)
root.right.right.left.right.right = TreeNode(1)
assert s.longestZigZag(root) == 3

root = TreeNode(1)
root.right, root.left = TreeNode(1), TreeNode(1)
root.left.right = TreeNode(1)
root.left.right.left, root.left.right.right = TreeNode(1), TreeNode(1)
root.left.right.left.right = TreeNode(1)
assert s.longestZigZag(root) == 4

root = TreeNode(1)
assert s.longestZigZag(root) == 0